package leetcode.easy;

/**
 * ClassName: $69_Sqrt
 * Description:
 * date: 2021-10-25 16:51
 *
 * @author liyifan
 */
public class $69_Sqrt {
    public int mySqrt(int x) {
        if (x == 0) return 0;
        int left = 1;
        int right = x;

        while (left <= right) {
            int mid = left + (right - left) / 2;
            int sqrt = x / mid;
            if (sqrt == mid) {
                return mid;
            } else if(mid > sqrt) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return right;
    }
}
